package com.acwing.partition11;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class AC1057股票买卖IV {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), k = Integer.parseInt(s[1]);
        int[] nums = new int[n];
        s = reader.readLine().split("\\s+");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(s[i]);
        writer.write(dynamicProgramming(nums, k) + "\n");
        writer.flush();
    }

    private static int dynamicProgramming(int[] nums, int k) {
        //dp[i][j][k]表示前i天完成的交易有j单，且当前的决策是k的方案
        int[][][] dp = new int[nums.length + 1][k + 1][2];
        //初始化数据为负无穷，表示不希望从这个状态进行转移，比如dp[i][0][1]，一次交易都没有，不可能出现手中持有股票的情况
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j][0] = dp[i][j][1] = -0x3f3f3f3f;
            }
        }
        //初始化合法的起点，后续的状态转移根据这个来
        for (int i = 0; i <= nums.length; i++) dp[i][0][0] = 0;
        for (int i = 1; i <= nums.length; i++) {
            int price = nums[i - 1];
            for (int j = 1; j <= k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + price);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - price);
            }
        }
        int ans = 0;
        for (int i = 0; i <= k; i++) ans = Math.max(ans, dp[nums.length][i][0]);
        return ans;
    }
}
